import java.util.*;

class Partition {
    int startAddress; // 分区的起始地址
    int size;         // 分区大小（KB）
    boolean isFree;   // 分区是否空闲
    Integer processId = null; // 使用该分区的进程ID

    public Partition(int startAddress, int size) {
        this.startAddress = startAddress;
        this.size = size;
        this.isFree = true;
    }

    /**
     * 为指定的进程分配内存。
     */
    public void allocate(Integer processId, int processSize) {
        if (processSize <= size && isFree) { // 确保有足够的空间并且分区是空闲的
            this.processId = processId;
            isFree = false;
            size = processSize;
        }
    }

    /**
     * 将分区标记为空闲状态。
     */
    public void free() {
        isFree = true;
        processId = null;
    }

    @Override
    public String toString() {
        return "地址: " + startAddress + ", 大小: " + size + "KB, 空闲: " + isFree + ", 进程 ID: " + processId;
    }
}

class MemoryManager {
    List<Partition> partitions; // 内存中的所有分区列表
    int totalSize;              // 总内存大小

    /**
     * 构造函数初始化内存管理器。
     */
    public MemoryManager(int totalSize) {
        this.totalSize = totalSize;
        partitions = new ArrayList<>();
        partitions.add(new Partition(0, totalSize)); // 初始时整个内存是一个大空闲块
    }

    /**
     * 批量为多个进程分配内存。
     */
    public void allocate(Map<Integer, Integer> processSizes) {
        for (Map.Entry<Integer, Integer> entry : processSizes.entrySet()) {
            Integer processId = entry.getKey();
            int processSize = entry.getValue();

            // 查找最坏适应算法下的空闲块
            Partition selectedPartition = partitions.stream()
                    .filter(p -> p.isFree && p.size >= processSize)
                    .max(Comparator.comparingInt(p -> p.size)).orElse(null);

            if (selectedPartition != null) {
                int remainingSize = selectedPartition.size - processSize;
                selectedPartition.allocate(processId, processSize);
                if (remainingSize > 0) {
                    // 如果有剩余空间，则创建新的空闲分区
                    partitions.add(new Partition(selectedPartition.startAddress + processSize, remainingSize));
                }
                System.out.println("已为进程 " + processId + " 分配 " + processSize + "KB 在地址 " + selectedPartition.startAddress);
            } else {
                System.out.println("没有找到适合进程 " + processId + " 的分区，所需大小 " + processSize + "KB");
            }
        }
    }

    /**
     * 根据进程ID回收内存。
     */
    public void free(int processId) {
        for (Iterator<Partition> it = partitions.iterator(); it.hasNext(); ) {
            Partition partition = it.next();
            if (partition.processId != null && partition.processId.equals(processId)) {
                partition.free();
                mergeFreePartitions();
                System.out.println("已释放进程 " + processId + " 的内存");
                return;
            }
        }
        System.out.println("未找到已分配给进程 " + processId + " 的分区");
    }

    /**
     * 合并相邻的空闲分区。
     */
    private void mergeFreePartitions() {
        partitions.sort(Comparator.comparingInt(p -> p.startAddress));
        for (int i = 0; i < partitions.size() - 1; i++) {
            Partition current = partitions.get(i);
            Partition next = partitions.get(i + 1);
            if (current.isFree && next.isFree) {
                current.size += next.size;
                partitions.remove(i + 1);
                i--;  // 删除后重新检查当前索引
            }
        }
    }

    /**
     * 显示当前内存分区状态。
     */
    public void display() {
        System.out.println("内存分区：");
        for (Partition partition : partitions) {
            System.out.println(partition);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入总内存大小 (KB): ");
        int totalSize;
        try {
            totalSize = scanner.nextInt();
            if (totalSize <= 0) throw new IllegalArgumentException("内存大小必须为正数.");
        } catch (Exception e) {
            System.out.println("无效输入: " + e.getMessage());
            return;
        }

        MemoryManager memoryManager = new MemoryManager(totalSize);

        while (true) {
            System.out.println("请选择操作: 1-分配, 2-释放, 3-显示, 4-退出");
            int choice;
            try {
                choice = scanner.nextInt();
            } catch (Exception e) {
                System.out.println("无效输入: " + e.getMessage());
                scanner.next();  // 清除无效输入
                continue;
            }

            switch (choice) {
                case 1:
                    Map<Integer, Integer> processSizes = new HashMap<>();
                    System.out.print("请输入要分配的进程数量: ");
                    int numProcesses;
                    try {
                        numProcesses = scanner.nextInt();
                        if (numProcesses <= 0)
                            throw new IllegalArgumentException("进程数量必须为正数.");
                    } catch (Exception e) {
                        System.out.println("无效输入: " + e.getMessage());
                        scanner.next(); // 清除无效输入
                        continue;
                    }
                    for (int i = 0; i < numProcesses; i++) {
                        System.out.print("请输入进程ID: ");
                        int processId;
                        try {
                            processId = scanner.nextInt();
                        } catch (Exception e) {
                            System.out.println("无效输入: " + e.getMessage());
                            scanner.next(); // 清除无效输入
                            i--; // 重复此进程输入
                            continue;
                        }
                        System.out.print("请输入进程 " + processId + " 的大小 (KB): ");
                        int processSize;
                        try {
                            processSize = scanner.nextInt();
                            if (processSize <= 0)
                                throw new IllegalArgumentException("进程大小必须为正数.");
                        } catch (Exception e) {
                            System.out.println("无效输入: " + e.getMessage());
                            scanner.next(); // 清除无效输入
                            i--; // 重复此进程输入
                            continue;
                        }
                        processSizes.put(processId, processSize);
                    }
                    memoryManager.allocate(processSizes);
                    break;
                case 2:
                    System.out.print("请输入要释放的进程ID: ");
                    int processId;
                    try {
                        processId = scanner.nextInt();
                    } catch (Exception e) {
                        System.out.println("无效输入: " + e.getMessage());
                        scanner.next();  // 清除无效输入
                        continue;
                    }
                    memoryManager.free(processId);
                    break;
                case 3:
                    memoryManager.display();
                    break;
                case 4:
                    System.out.println("退出程序...");
                    System.exit(0);
                default:
                    System.out.println("未知选项: " + choice);
            }
        }
    }
}